Geometric comparison¶
- Mytaxi, Daimler: How similar are our routes vs. Google?
-Need reliable way to measure this!
Methodology¶
- Review state-of-the-art
- Create synthetic test cases (controlled outcome)
- Test algorithms for:
- Meaningfulness
- Performance
Synthetic test cases¶
- Emulate common challenging scenarios
- Detours
- Very short/long route sensitivity
- Noise (trace vs match)
- Shifts (different maps)
- Sparseness (different sampling)
- Control the desired outcome
- Total of 39 synthetic tests
Scenarios: basic¶
Test common and basic scenarios.
In [2]:
render_basic_scenarios()
Scenarios: detours¶
Test sensitivity to detour severity
In [3]:
render_detours()
Scenarios: shifts¶
Test resiliance to shifted maps.
In [4]:
render_shifts()
Scenarios: noise¶
Test resiliance to noisy data (e.g. suitability as match success classifier)
In [5]:
render_noisy()
Scenarios: subsampling¶
Test resiliance to subsampled routes
In [6]:
render_sparse()
Scenario: start/end point mismatch¶
Test resiliance to start/end point mismatch
In [7]:
render_start_end_mismatch()
Algorithms¶
Approaches:
| approach | "detour" sensitivity | "bias" sensitivity | range | speed | examples |
|---|---|---|---|---|---|
| distance | high | low | 0-inf | slow/fast | Hausdorff, Frechet, centroids |
| area | low | high | 0-inf | fast | AUC |
| correlation | medium | medium | 0-100% | slow/fast | AUC normalized, CIR, CPR |
| hybrid | high | high | 0-inf | slow | BOC |
- detour sensitivity: whether it captures occasional, well pronnounced differences
- bias sensitivity: whether it captures systemic, small differences
Hausdorff distance¶
Maximum of minimum distance possible between any two pairs of points of the geometry.
In [8]:
Image('_img/hausdorff.png', embed=True)
Out[8]:
Frechet distance¶
The Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves.
In [9]:
Image('_img/frechet.png', embed=True, width=500)
Out[9]:
Dynamic Time Warping¶
Compares phased-in geometry/sequence distance.
In [10]:
Image('_img/dtw.png', embed=True, width=300)
Out[10]:
Centroid distance¶
Calculates distance between geometry centroids/centers-of-mass
In [11]:
l1 = test_detour_big_very_short_1.to_linestring(convert_to_utm=True)
l2 = test_detour_big_very_short_2.to_linestring(convert_to_utm=True)
plt.plot(*zip(*l1.coords))
plt.plot(*zip(*l2.coords))
plt.scatter(l1.centroid.x, l1.centroid.y)
plt.scatter(l2.centroid.x, l2.centroid.y)
Out[11]:
AUC¶
Calculates area defined between the two geometries/curves.
In [12]:
utm_linestring_1 = test_detour_big_very_short_1.to_linestring(convert_to_utm=True)
utm_linestring_2 = test_detour_big_very_short_2.to_linestring(convert_to_utm=True)
sg.Polygon(list(utm_linestring_1.coords) + list(utm_linestring_2.coords)[::-1])
Out[12]:
AUC normalized¶
Calculates area defined between the two geometries/curves and normalizes it by envelope containing both geometries.
In [2]:
utm_linestring_1 = test_detour_big_very_short_1.to_linestring(convert_to_utm=True)
utm_linestring_2 = test_detour_big_very_short_2.to_linestring(convert_to_utm=True)
polygon = sg.Polygon(list(utm_linestring_1.coords) + list(utm_linestring_2.coords)[::-1])
plt.plot(*zip(*list(polygon.envelope.boundary.coords)))
plt.plot(*zip(*list(polygon.boundary.coords)))
Out[2]:
BOCS (Bias-Outlier Composite Score)¶
Geometric mean of max distance and total AUC.
In [3]:
l1 = test_detour_big_very_short_1.to_linestring(convert_to_utm=True)
l2 = test_detour_big_very_short_2.to_linestring(convert_to_utm=True)
plt.plot(*zip(*l1.coords))
plt.plot(*zip(*l2.coords))
plt.scatter(l1.centroid.x, l1.centroid.y)
plt.scatter(l2.coords[13][0] + 85, l2.coords[13][1] - 28)
Out[3]:
PMR (Point Match Ratio)¶
% of points close enough to other geometry
In [7]:
corridor_1 = utm_linestring_1.buffer(10)
corridor_2 = utm_linestring_2.buffer(10)
display('All points:')
display(corridor_1.union(corridor_2))
display('Point matches:')
display(corridor_1.intersection(corridor_2))
Levenshtein (edit) distance¶
Minimum number of edits required to transform encoded polyline of one to the other.
In [8]:
Image('_img/levensthein.png', embed=True, width=400)
Out[8]:
Results¶
Accuracy in synthetic tests¶
In [10]:
configs = {
'hausdorff': {'name': 'hausdorff', 'params': {}},
# TOO SLOW 'frechet': {'name': 'frechet', 'params': {}},
# TOO SLOW 'dtw': {'name': 'dtw', 'params': {}},
'centroids': {'name': 'centroids', 'params': {}},
'auc': {'name': 'auc', 'params': {}},
'auc_norm': {'name': 'auc', 'params': {'normalized': True}},
'bocs': {'name': 'bocs', 'params': {}},
'pmr': {'name': 'pmr', 'params': {}},
'pmr_lenient': {'name': 'pmr', 'params': {'buffer': 50}},
'pmr_strict': {'name': 'pmr', 'params': {'buffer': 3}},
'levensthein': {'name': 'levenshtein', 'params': {}},
}
tests = sorted(glob.glob('data/*.json'))
results = run_tests(tests, configs)
df = pd.DataFrame(results).transpose()
Score correlation:
In [11]:
sns.heatmap(df.corr())
Out[11]:
Accuracy in real world cases¶
100 tests, Berlin coverage map:
In [100]:
results_df = pd.read_csv('results/routes_comparison.csv')
plot_all(results_df)
Results:
In [94]:
create_debug_artifacts(results_df)
Conclusions¶
- PMR most meaningful when comparing to others
- Ratio is much more understandable
- Does not capture severity of differences
- Hausdorff best candidate for binary classifier:
- Are both routes the same?
- Determine match success
Code¶
Package: route_quality.metrics.geometry
Script: geometry-comparison.py
Next¶
- Find accuracy of prime metrics as match success classifiers
- Continue evaluating different metrics for different purposes
Preliminary tests¶
In [15]:
analyze_results()
Bonus: Route stats¶
Length comparison¶
In [394]:
compare_distributions(metrics, 'length', 'Length [km]', palette=palette)
ETA comparison¶
In [396]:
compare_distributions(metrics, 'eta', 'ETA [min]', palette=palette)
Speed comparison¶
In [397]:
compare_distributions(metrics, 'speed', 'Speed [km/h]', palette=palette)
Speed diffs vs Google¶
In [398]:
df['das-traffic'] = df['speed_das-traffic'] - df['speed_google']
df['das'] = df['speed_das'] - df['speed_google']
vs = pd.melt(df[['route_id', 'das-traffic', 'das']], id_vars=['route_id'], var_name='provider', value_vars=['das-traffic', 'das'], value_name='speed_diff')
compare_distributions(vs, 'speed_diff', 'Speed diff. to Google [km/h]', palette=palette)
ETA vs Length¶
In [404]:
f = plt.figure()
sns.lmplot(data=metrics.drop(index=24).sort_values('speed', ascending=True),
x='length', y='eta', hue='provider', palette=palette, markers='.')
plt.xlabel('Duration [km]')
plt.ylabel('ETA [min]')
Out[404]:
